package com.cn.algorithm02.class20;


import java.util.HashMap;

/***
 * @author: hels
 * @description: 贴纸“abc”“bba”“cck”要贴出“aabbbbc”的样式(2)
 * 有一组字符串贴纸，每个不限张数，可以自由剪裁。使用这些贴纸拼出目标字符串，至少需要几张贴纸。
 * 所有的字符串都是小写字母。
 **/
public class C01_StickersToSpellWord {
    public static void main(String[] args) {
        String[] strArr = {"ad",  "bc", "abc", "xyz", "dadow", "isiij", "awei", "woncnjhd", "adiop"};
        String target = "abcabcaozypbdpxscadbcabcaoabcyy";
        long l1= System.currentTimeMillis();
//        System.out.println(minNum(strArr, target));
        long l2 = System.currentTimeMillis();
//        System.out.println(minNum2(strArr, target));
        long l3 = System.currentTimeMillis();
        System.out.println(minNum3(strArr, target));
        long l4 = System.currentTimeMillis();
    }

    // 三、增加dp缓存表
    public static int minNum3(String[] strikerArr, String target) {
        int N = strikerArr.length;
        // 将字符串数组字母用二维数组统计
        int[][] strikers = new int[N][26];
        for (int i = 0; i < N; i++) {
            char[] strikerChar = strikerArr[i].toCharArray();
            for (char ch : strikerChar) {
                strikers[i][ch - 'a']++;
            }
        }
        HashMap<String, Integer> dp = new HashMap<>();

        Integer result = process3(strikers, target, dp);
        return result == Integer.MAX_VALUE ? -1 : result;
    }

    private static Integer process3(int[][] strikers, String target, HashMap<String, Integer> dp) {
        if (dp.containsKey(target)) {
            return dp.get(target);
        }

        char[] targetChar = target.toCharArray();
        int[] tcounter = new int[26];
        for (char ch : targetChar) {
            tcounter[ch - 'a']++;
        }

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < strikers.length; i++) {
            int[] striker = strikers[i];
            // 根据第一个字母剪枝
            if (striker[targetChar[0] - 'a'] > 0) {
                String rest = minus2(striker, tcounter);

                min = Math.min(min, process2(strikers, rest.toString()));
            }
        }
        Integer ans = min + (min == Integer.MAX_VALUE ? 0 : 1);
        dp.put(target, ans);
        return ans;
    }

    // 二、剪枝
    public static int minNum2(String[] strikerArr, String target) {
        int N = strikerArr.length;
        // 将字符串数组字母用二维数组统计
        int[][] strikers = new int[N][26];
        for (int i = 0; i < N; i++) {
            char[] strikerChar = strikerArr[i].toCharArray();
            for (char ch : strikerChar) {
                strikers[i][ch - 'a']++;
            }
        }
        Integer result = process2(strikers, target);
        return result == Integer.MAX_VALUE ? -1 : result;
    }

    private static Integer process2(int[][] strikers, String target) {
        if (target.length() == 0) {
            return 0;
        }

        char[] targetChar = target.toCharArray();
        int[] tcounter = new int[26];
        for (char ch : targetChar) {
            tcounter[ch - 'a']++;
        }

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < strikers.length; i++) {
            int[] striker = strikers[i];
            // 根据第一个字母剪枝
            if (striker[targetChar[0] - 'a'] > 0) {
                String rest = minus2(striker, tcounter);

                min = Math.min(min, process2(strikers, rest.toString()));
            }
        }
        return min + (min == Integer.MAX_VALUE ? 0 : 1);
    }

    private static String minus2(int[] striker, int[] tcounter) {
        StringBuffer rest = new StringBuffer();
        for (int j = 0; j < 26; j++) {
            // 两个字母计数器相减
            int num =  tcounter[j] - striker[j];
            if (num > 0) {
                for (int k = 0; k < num; k++) {
                    rest.append((char) (j + 'a'));
                }
            }
        }
        return rest.toString();
    }


    // 一、尝试方法
    public static int minNum(String[] stickers, String target) {
        Integer result = process1(stickers, target);
        return result == Integer.MAX_VALUE ? -1 : result;
    }

    // 递归
    public static Integer process1(String[] stickers, String target) {
        if (target.length() == 0) {
            return 0;
        }

        int min = Integer.MAX_VALUE;
        for (String str : stickers) {
            String rest = minus(str, target);
            if (rest.length() != target.length()) {
                min = Math.min(min, process1(stickers, rest));
            }
        }
        return min + (min == Integer.MAX_VALUE ? 0 : 1);
    }

    public static String minus(String str, String target) {
        char[] s1 = str.toCharArray();
        char[] c2 = target.toCharArray();
        int[] counter = new int[26];
        for (char ch : s1) {
            counter[ch - 'a']--;
        }
        for (char ch : c2) {
            counter[ch - 'a']++;
        }

        StringBuffer newTarget = new StringBuffer();
        for (int i = 0; i < 26; i++) {
            if (counter[i] > 0) {
                for (int j = 0; j < counter[i]; j++) {
                    newTarget.append((char) (i + 97));
                }
            }
        }
        return newTarget.toString();
    }
}
